home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part1 / 8191 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  2.2 KB
  1. Path: newsroom.hitc.com!usenet
  2. From: psand@eos.hitc.com (G. Patrick Sand)
  3. Newsgroups: comp.lang.c++,
  4. Subject: Re: Tough FACTORIAL math problem...
  5. Date: 15 Feb 1996 17:08:15 GMT
  6. Organization: Hughes Aircraft (EOSDIS)
  7. Message-ID: <4fvp9v$sso@newsroom.hitc.com>
  8. References: <4fr8be$ass@news.iconn.net> <31224679.6193@born.com>
  9. NNTP-Posting-Host: 155.157.118.56
  10. Mime-Version: 1.0
  11. X-Newsreader: WinVN 0.99.3
  12.  
  13. In article <31224679.6193@born.com>, clelaj@born.com says...
  14. >
  15. >The Crow wrote:
  16. >> 
  17. >> Here is what I am trying to do, I want to find the last NON-ZERO digit
  18. > of a
  19. >> given factorial.  For instance,
  20. >> 
  21. >> 5! = 120
  22. >> 
  23. >> so the last non-zero digit is 2.  I want to be able to do this up to 1
  24. >000.
  25. [SNIP!!!]
  26.  
  27. Here are two other approaches, which should take up very little space and 
  28. be lightning quick:
  29.  
  30. Since you only care about the smallest non-zero digit, just multiply the 
  31. last smallest non-zero digit by the next number's smallest non-zero 
  32. digit!
  33. You can easily test for the result being a multiple of 10.  This requires 
  34. a bit of bookkeeping for dealing with numbers like 10, 100,
  35. 200, 350, etc. but that's fairly easy to handle...Heck, you could write 
  36. three nested for(...) loops to handle going from 1-1000, although some 
  37. purists will balk...
  38.  
  39. If you want to minimize the testing for zero-digits, build yourself a 9x9 
  40. matrix which holds the least-significant digit of the product of 
  41. (i+1)*(j+1)
  42. [i,j are C/C++ indexes ranging from 0-8].  You then can use three nested 
  43. for(...) loops and just select the row (new number lsd) and column (lsd 
  44. of previous factorial) and look it up...
  45.  
  46. The nice thing with the second approach is that it can be easily modified 
  47. to do this in MOD J, where J is not 10.  Just adjust the for(...) loops 
  48. to range between 0 and J-1 and have the matrix be (J-1)x(J-1) big...You 
  49. just pay for the looping and lookup time, but you don't have to multiply 
  50. things and divide...
  51.  
  52. Hope this helps...
  53. -- 
  54. G. Patrick Sand
  55. psand@eos.hitc.com
  56. PatSand@aol.com
  57. (301) 925-0791
  58. "Travel Light But Right..."
  59. Microsoft Network is prohibited from redistributing 
  60. this work in any form, in whole or in part.   License 
  61. to distribute this individual post is available to Microsoft
  62. for $999. Posting without permission constitutes an 
  63. agreement to these terms...gps
  64.  
  65.